package com.zh.javaguide.算法;

import org.junit.jupiter.api.Test;

import java.util.HashSet;

/**
 * Copyright (C) 广州中和互联网技术有限公司
 * 最长回文串
 *
 * @author 范家微 fanjiawei@borche.cn
 * @date :2021/1/29 17:58
 */

public class Palindrome {

	/**
	 * 验证回文串
	 * <p>
	 * LeetCode: 给定⼀个字符串，验证它是否是回⽂串，只考虑字⺟和数字字符，可以忽略字⺟的⼤⼩
	 * 写。 说明：本题中，我们将空字符串定义为有效的回⽂串。
	 */

	public Boolean isPalindrome(String s) {
		if (s.length() == 0) {

			return true;
		}


		int l = 0, r = s.length() - 1;
		while (l < r) {
			if (!Character.isLetterOrDigit(s.charAt(l))) {
				l++;
			} else if (!Character.isLetterOrDigit(s.charAt(r))) {
				r--;
			} else {
				if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) {
					return false;

				} else {
					l++;
					r--;
				}
			}
		}

		return true;
	}


	/**
	 * 获取最长回文串
	 * <p>
	 * 给定⼀个包含⼤写字⺟和⼩写字⺟的字符串，找到通过这些字⺟构造成的最⻓的回⽂
	 * 串。在构造过程中，请注意区分⼤⼩写。⽐如 "Aa" 不能当做⼀个回⽂字符串。注 意:假设字符串
	 * 的⻓度不会超过 1010。
	 *
	 * @param str
	 * @return
	 */
	public int getLongestPalindrome(String str) {
		int count = 0;
		if (str.length() == 0) {
			return 0;
		}
		HashSet<Character> characters = new HashSet<>();
		char[] chars = str.toCharArray();
		for (char c : chars) {
			if (!characters.add(c)) {
				characters.remove(c);
				count++;
			}
		}
		return characters.size() > 0 ? count * 2 + 1 : count * 2;
	}

	/**
	 * 测试最长回文串
	 */
	@Test
	public void test() {
		System.out.println(getLongestPalindrome("abbbc"));
	}
}
